package basic.study.algorithms.solution.Stringmatching.multi;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;

/**
 * @author Kevin
 * @date 2020/2/16 19:23
 */
public class ACAutoMata {
    private ACNode root;

    public ACAutoMata() {
        this.root = new ACNode("/");
    }
    //先构建一颗trie树，然后下一个函数建立fail
    private void insert(String pattern) {
        ACNode node = this.root;
        int len = pattern.length();
        for (int i = 0; i < len; i++) {
            String c = pattern.charAt(i) + "";
            if (Objects.isNull(node.children.get(c))) {
                node.children.put(c, new ACNode(c));
            }
            node = node.children.get(c);
        }

        node.isEndingChar = true;
        node.length = pattern.length();
    }

    private void buildFailurePointer() {
        ACNode root = this.root;
        LinkedList<ACNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()) {//广度遍历,按照Trie树每层遍历
            ACNode p = queue.pop();

            for (ACNode pc: p.children.values()) {
                if (Objects.isNull(pc)) {
                    continue;
                }

                if (p == root) {
                    pc.fail = root;
                } else {
                    ACNode q = p.fail;//找到fail对应Node节点q
                    while (Objects.nonNull(q)) {
                        ACNode qc = q.children.get(pc.data);//找到fail对应Node节点q的下一节点qc
                        if (Objects.nonNull(qc)) {//fail对应Node节点的下一节点之一，和p节点下一节点pc有重
                            pc.fail = qc;
                            break;
                        }
                        q = q.fail;//继续横向建立fail，可以想象成蜗牛的一层壳纹理
                    }
                    if (Objects.isNull(q)) {
                        pc.fail = root;
                    }
                }
                queue.add(pc);
            }
        }
    }
    //建立完Trie树和fail节点
    public Boolean match (String text) {
        ACNode root = this.root;
        ACNode p = root;

        int n = text.length();
        for (int i = 0; i < n; i++) {
            String c = text.charAt(i) + "";
            while (Objects.isNull(p.children.get(c)) && p != root) {
                p = p.fail;
            }

            p = p.children.get(c);
            if (Objects.isNull(p)) {
                p = root;
            }

            ACNode tmp = p;
            while (tmp != root) {//对于text的每个位置i，都得使用fail节点“遍历”一遍Tire树
                if (tmp.isEndingChar == true) {//不是root节点，且是最后一结点才生效
                    System.out.println("Start from " + (i - p.length + 1));
                    return true;
                }
                tmp = tmp.fail;
            }
        }
        return false;
    }

    public static boolean match(String text, String[] patterns) {
        ACAutoMata automata = new ACAutoMata();
        for (String pattern: patterns) {
            automata.insert(pattern);//构建Trie树
        }

        automata.buildFailurePointer();//构建
        return automata.match(text);
    }

    public class ACNode {
        private String data;
        private Map<String, ACNode> children;
        private Boolean isEndingChar;
        private Integer length;
        private ACNode fail;

        public ACNode(String data) {
            this.data = data;
            this.children = new HashMap<>();
            this.isEndingChar = false;
            this.length = 0;
            this.fail = null;
        }
    }


}
